# -*- coding: utf-8 -*-

"""剑指 Offer II 044. 二叉树每层的最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
          1
         / \
        3   2
       / \   \  
      5   3   9

示例2：
输入: root = [1,2,3]
输出: [1,3]
解释:
          1
         / \
        2   3

示例3：
输入: root = [1]
输出: [1]

示例4：
输入: root = [1,null,2]
输出: [1,2]
解释:      
           1 
            \
             2     

示例5：
输入: root = []
输出: []

提示：
二叉树的节点个数的范围是 [0,10^4]
-2^31 <= Node.val <= 2^31 - 1"""

import math
from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    """用一个游标，标记当前待访问节点队列中最近的一层的最后一个节点"""
    def largestValues(self, root: TreeNode):
        lValues = []
        if root:
            wait_access_nodes_queue = deque([])
            lValues.append(root.val)
            wait_access_nodes_queue.append(root)
            end_node = root
            largest = -math.inf
            while True:
                try:
                    node = wait_access_nodes_queue.popleft()

                    if node.left:
                        wait_access_nodes_queue.append(node.left)
                        largest = max(largest, node.left.val)
                    if node.right:
                        wait_access_nodes_queue.append(node.right)
                        largest = max(largest, node.right.val)
                    
                    if end_node is node:
                        end_node = wait_access_nodes_queue.pop()
                        wait_access_nodes_queue.append(end_node)
                        lValues.append(largest)
                        largest = -math.inf

                except IndexError:
                    break
        return lValues
            

